__all__ = ['quick_sort', 'quick_sort_fast']


def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] < pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i


def quick_sort_sub(array, low, high):
    if low < high:
        pivot = partition(array, low, high)
        quick_sort_sub(array, low, pivot-1)
        quick_sort_sub(array, pivot+1, high)


def quick_sort(array: list):
    return quick_sort_sub(array, 0, len(array)-1)


def quick_sort_fast_sub(array, low, high):
    """
    基于左右双索引进行划分子序列               | pivot
      *                               *
    [73, 44, 30, 57, 82, 74, 55, 65, 33, | 63  ]
    exchange
    [33, 44, 30, 57, 82, 74, 55, 65, 73, | 63  ]
                      *      *
    [33, 44, 30, 57, 82, 74, 55, 65, 73, | 63  ]
    exchange
                          *
    [33, 44, 30, 57, 55, 74, 82, 65, 73, | 63  ]
                     r*  l*
    [33, 44, 30, 57, 55, 74, 82, 65, 73, | 63  ]

    [33, 44, 30, 57, 55, |63|, 82, 65, 73,  74  ]

    :param array:
    :param low:
    :param high:
    :return:
    """
    if low >= high:
        return
    pivot = array[high] # 取最右边的的元素作为pivot
    left = low
    right = high-1

    while left <= right:
        # 从左开始扫描，直到遇到大于等于pivot
        while left <= right and array[left] < pivot:
            left += 1
        while left <= right and array[right] > pivot:
            right -= 1
        if left <= right:
            array[left], array[right] = array[right], array[left]
            left, right = left+1, right-1
    # 将pivot和left index交换
    array[left], array[high] = array[high], array[left]

    # 子序列递归
    quick_sort_fast_sub(array, low, left-1)
    quick_sort_fast_sub(array, left+1, high)


def quick_sort_fast(array: list):
    return quick_sort_fast_sub(array, 0, len(array)-1)